package org.example.myleet.p587;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public int[][] outerTrees(int[][] trees) {
        List<int[]> edgePoints = new ArrayList<>(trees.length);
        boolean[] chose = new boolean[trees.length];
        //找到最左边的点
        int mostLeftPontI = 0;
        for (int i = 1; i < trees.length; ++i) {
            if (trees[i][0] < trees[mostLeftPontI][0]) {
                mostLeftPontI = i;
            }
        }
        edgePoints.add(trees[mostLeftPontI]);
        chose[mostLeftPontI] = true;
        //使用Javis算法依次将能形成凸包的点加入到结果中
        int lastPointI = mostLeftPontI;
        int curPointI;
        do {
            curPointI = (lastPointI + 1) % trees.length;
            for (int i = 0; i < trees.length; ++i) {
                if (cross(trees[lastPointI], trees[curPointI], trees[i]) < 0) {
                    //如果出现i在lastPoint-》curPoint的右侧，说明i在更外圈，选i
                    curPointI = i;
                }
            }
            //此时已经找出下一个最外围的curPoint，然后需要观察是否有lastPoint-》curPoint线上的点，有的话也加入到凸包点结果中
            for (int i = 0; i < trees.length; ++i) {
                if (chose[i] || i == curPointI || i == lastPointI) {
                    continue;
                }
                if (cross(trees[lastPointI], trees[curPointI], trees[i]) == 0) {
                    //共线
                    edgePoints.add(trees[i]);
                    chose[i] = true;
                }
            }
            //curPoint加入到凸包点，标记
            if (!chose[curPointI]) {
                edgePoints.add(trees[curPointI]);
                chose[curPointI] = true;
            }
            //以curPointI为基础找下一个点，直到curPointI返回到最左侧的点
            lastPointI = curPointI;
        } while (curPointI != mostLeftPontI);
        int[][] result = new int[edgePoints.size()][];
        for (int i = 0; i < edgePoints.size(); ++i) {
            result[i] = edgePoints.get(i);
        }
        return result;
    }

    /**
     * 计算pq向量与qr向量的叉积
     * 如果叉积为正数，则说明pq与qr在逆时针方向上夹角小于180度（右手定则），此时r在pq向量的左侧
     * 如果叉积为0，说明pq与qr平行
     * 如果叉积为负数，则说明pq与qr在逆时针方向上夹角大于180度（右手定则），此时r在pq向量的右侧
     */
    private int cross(int[] p, int[] q, int[] r) {
        int x1 = q[0] - p[0];
        int y1 = q[1] - p[1];
        int x2 = r[0] - q[0];
        int y2 = r[1] - q[1];
        return x1 * y2 - x2 * y1;
    }

    private boolean equalPoint(int[] p, int[] q) {
        return p[0] == q[0] && p[1] == q[1];
    }
}
